﻿#include <iostream>
#include <iomanip>
#include "complex_sort.h"

using namespace std;

void Complexsort::PrintResult(int* Arr, int n)
{
    if (n <= 1 || Arr == nullptr)
    {
        return;
    }
    for (int i = 0; i < n; i++)
    {
        cout << setw(4) << Arr[i];
    }
    cout << endl;
}

//获取希尔增量，返回Gap数组，如果要使用其他增量，可更改此函数
void Complexsort::GetShellGap(vector<int> &Gap, int n)
{
    if (n <= 1)
    {
        return;
    }
    Gap.clear();
    for (int i = n >> 1; i >= 1; i = i >> 1)//右移1即除以2
    {
        Gap.push_back(i);
    }

    cout << "shell gap :" << endl;
    for (vector<int>::iterator itergap = Gap.begin(); itergap != Gap.end(); itergap++)
    {
       
        cout << setw(4) << *itergap;
    }
    cout << endl;
}


//void Complexsort::ShellSort(const vector<int>& Gap, int* Arr, int n)
//{
//    if (n <= 1|| Arr==nullptr|| Gap.empty())
//    {
//        return;
//    }
//    for (vector<int>::const_iterator itergap = Gap.begin(); itergap != Gap.end(); itergap++)//每次执行完更改步长
//    {
//        for (int i = *itergap; i < n; i++)//分组，共*itergap组，每组插入排序从第二个元素开始，所以初始i = *itergap；
//        {
//            //每一组内部执行插入排序
//            int InsertVal = Arr[i];
//            int j = i - *itergap;
//            for (; j >= 0; j -= *itergap)
//            {
//                if (Arr[j] > InsertVal)
//                {
//                    Arr[j+*itergap] = Arr[j];
//                }
//                else
//                {
//                    break;//如果在已排序区间内找到<=插入值的数，则退出
//                }
//            }
//            Arr[j+*itergap] = InsertVal;
//        }
//    }
//
//}

void Complexsort::ShellSort(const vector<int>& Gap, int* Arr, int n)
{
    if (n <= 1 || Arr == nullptr || Gap.empty())
    {
        return;
    }
    for (vector<int>::const_iterator itergap = Gap.begin(); itergap != Gap.end(); itergap++)//每次执行完更改步长
    {
        for (int i = *itergap; i < n; i++)//分组，共*itergap组，每组插入排序从第二个元素开始，所以初始i = *itergap；
        {
            //每一组内部执行插入排序
            int InsertVal = Arr[i];
            int j = i ; //j不会为负
            for (; j >= *itergap; j -= *itergap)
            {
                if (Arr[j - *itergap] > InsertVal)
                {
                    Arr[j ] = Arr[j- *itergap];
                }
                else
                {
                    break;//如果在已排序区间内找到<=插入值的数，则退出
                }
            }
            Arr[j] = InsertVal;
        }
    }

}
//由于递归操作，每次数组的下标不确定，所以需要传入当前数组的下标范围
void Complexsort::RecurseMergeSort(int* Arr, int start, int end)
{
    if (start>= end ||Arr == nullptr)//只有一个元素无需排序
    {
        return;
    }
    //将传入的数组对半分
    int LeftStart = start;
    int LeftEnd   = (start+end)/2;
    int RightStart = LeftEnd + 1;
    int RightEnd = end;

    //对数组左右两部分排序后合并
    RecurseMergeSort(Arr, LeftStart, LeftEnd);
    RecurseMergeSort(Arr, RightStart, RightEnd);

    Merge(Arr, LeftStart, LeftEnd, RightStart, RightEnd);
}

//合并并排序数组
void Complexsort::Merge(int* Arr, int Lstart, int Lend, int Rstart, int Rend)
{
    static int step = 1;
    cout << "step"<< step++ <<":" << endl;
    cout << " Lstart = " << Lstart << " Lend = " << Lend <<"   ****    Rstart = " << Rstart << " Rend = " << Rend << endl;

    int i = Lstart;
    int j = Rstart;
    int n = Rend - Lstart + 1;

    int* temp = new int[20];
    memset(temp, 0, 20);

    int k = 0;
    while (i <= Lend && j <= Rend)
    {
        if (Arr[i] < Arr[j])//把小的放进temp
        {
            temp[k++] = Arr[i++];
        }
        else
        {
            temp[k++] = Arr[j++];
        }
    }
    /*如果两个数组中有一个指针没有遍历完，则直接复制该数组剩余元素（该数组在上一步已经排序完成）*/
    while (i <= Lend)
    {
        temp[k++] = Arr[i++];
    }
    while (j <= Rend)
    {
        temp[k++] = Arr[j++];
    }
    cout << "cur Arr = ";
    for (k = 0; k < n; k++)
    {
        Arr[Lstart + k] = temp[k];
        cout << setw(4) << Arr[Lstart + k];
    }
    delete [] temp;
    cout << endl<<endl;
}
  


void Complexsort::IterMergeSort(int* Arr, int n )
{
    if (n <= 1 || Arr == nullptr)//只有一个元素无需排序
    {
        return;
    }

    for (int step = 1; step < n; step <<=1)
    {
        //将数组分成2*step大小的小块
        for (int index = 0; index < n; index += step * 2 )
        {
            Merge(Arr, index, min(index + step - 1, n - 1), min(index + step , n - 1), min(index + step + step - 1, n - 1));
        }
    }

}


int Complexsort::Partion(int* Arr, int start, int end)
{
    int i = start, j = end;//两个指针分别从头尾向相向出发
    int pivot = start;//选取基准点，如果选择左边，则要右边指针先动

    //打印信息
    cout <<"start = "<<start<<", end = "<<end<< ", Arr[start] = Arr["<<start<<"] = "<< Arr[start] << ":" << endl << "before partion, Arr = ";
    PrintResult(Arr, 11);

    while (i < j)
    {
        while (i < j && Arr[j] >= Arr[pivot]) //从后向前一直找到比基准点小的值
        {
            j--;
        }
        while (i < j && Arr[i] <= Arr[pivot])//从前向后一直找比基准点大的值
        {
            i++;
        }
        swap(Arr[i], Arr[j]);
    }

    pivot = i;
    swap(Arr[i], Arr[start]);//将pivot放入正确位置

    //打印信息
    cout << "pivot = " << i << endl;
    cout << "after partion,  Arr = ";
    PrintResult(Arr, 11);
    cout << endl;

    return pivot;
}


void Complexsort::RecurseQuickSort(int* Arr, int start, int end)
{
    int pivot;
    if (start < end)
    {
        pivot = Partion(Arr, start, end);
        RecurseQuickSort(Arr,start, pivot-1);
        RecurseQuickSort(Arr, pivot + 1, end);
    }
}

void Complexsort::IterQuickSort(int* Arr, int start, int end)
{
    int mystack[100] = {0};

    int top = -1;

    mystack[++top] = start;
    mystack[++top] = end;

    while (top >= 0)
    {
        end = mystack[top--];
        start = mystack[top--];

        int pivot = Partion(Arr, start, end);//找枢轴
        //枢轴左侧大于1个元素则对左侧进行操作，仅剩一个元素或没有则无需操作
        if (pivot - 1 > start)
        {
           mystack[++top] = start;
           mystack[++top] = pivot - 1;
        }
        //右侧同理
        if (pivot + 1 < end)
        {
            mystack[++top] = pivot + 1;
            mystack[++top] = end;
        }
    }

}

int main()
{
    int TestA[11] = { 158,76,95,33,59,258,62,12,5,23,11 };
    int len = 11;
    Complexsort Comsort;

    cout << "testA :" << endl;
    Comsort.PrintResult(TestA, len);
    cout << endl;

    Comsort.IterQuickSort(TestA, 0, 10);

    cout << "sort result :" << endl;
    Comsort.PrintResult(TestA, len);
}


//int main()
//{
//    int TestA[11] = { 158,76,95,33,59,258,62,12,5,23,11 };
//    int len = 11;
//    Complexsort Comsort;
//
//    cout << "testA :" << endl;
//    Comsort.PrintResult(TestA, len);
//    cout << endl;
//
//    Comsort.RecurseQuickSort(TestA,0,10);
//
//    cout << "sort result :" << endl;
//    Comsort.PrintResult(TestA, len);
//}


//int main()
//{
//    int TestA[11] = { 158,76,95,33,59,258,62,12,5,23,11 };
//    int len = 11;
//    Complexsort Comsort;
//
//    cout << "testA :" << endl;
//    Comsort.PrintResult(TestA, len);
//    cout << endl;
//
//    Comsort.IterMergeSort(TestA, len);
//
//    cout << "sort result :" << endl;
//    Comsort.PrintResult(TestA, len);
//}


//int main()
//{
//    int TestA[11] = { 158,76,95,33,59,258,62,12,5,23,11 };
//    int len = 11;
//    Complexsort Comsort;
//
//    cout << "testA :" << endl;
//    Comsort.PrintResult(TestA, len);
//    cout << endl;
//
//    Comsort.RecurseMergeSort(TestA,0,10);
//
//    cout << "sort result :" << endl;
//    Comsort.PrintResult(TestA, len);
//}

//int main()
//{
//    int TestA[11] = { 158,76,95,33,59,258,62,12,5,23,11 };
//    int len = 11;
//    Complexsort Comsort;
//    cout << "testA :" << endl;
//    Comsort.PrintResult(TestA, len);
//
//    vector<int> Gap;
//    Comsort.GetShellGap(Gap, len);
//    Comsort.ShellSort(Gap,TestA, len);
//
//    cout << "sort result :" << endl;
//    Comsort.PrintResult(TestA, len);  
//}